package compiler._dfa;

import compiler._nfa.Nfa;
import compiler._nfa.NfaInterpreter;
import compiler._nfa.NfaPair;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class DfaConstructor {
    //假定DFA状态机节点数不会超过254个
    private static final int MAX_DFA_STATE_COUNT = 254;
    private static final int ASCII_COUNT = 128;
    private static final int STATE_FAILURE = -1;
    private NfaPair nfaMachine = null;
    private NfaInterpreter nfaInterpreter = null;
    private ArrayList<Dfa> dfaList = new ArrayList<>();
    //使用二维数组表示DFA有限状态自动机
    private int[][] dfaStateTransformTable = new int[MAX_DFA_STATE_COUNT][ASCII_COUNT + 1];

    public DfaConstructor(NfaPair pair, NfaInterpreter nfaInterpreter) {
        this.nfaInterpreter = nfaInterpreter;
        //不要打印内部信息
        this.nfaInterpreter.debug = false;

        this.nfaMachine = pair;

        initTransformTable();
    }

    private void initTransformTable() {
        for (int i = 0; i < MAX_DFA_STATE_COUNT; i++)
            for (int j = 0; j <= ASCII_COUNT; j++) {
                dfaStateTransformTable[i][j] = STATE_FAILURE;
            }
    }

    public int[][] convertNfaToDfa() {

        System.out.println("convert nfa to dfa");
        System.out.println("Create DFA start node:");

        Set<Nfa> input = new HashSet<>();
        input.add(nfaMachine.startNode);
        Set<Nfa> nfaStartClosure = nfaInterpreter.e_closure(input);

        Dfa dfaStart = Dfa.newDfa(nfaStartClosure);
        dfaList.add(dfaStart);

        printDfa(dfaStart);

        int currentDfaIndex = 0;
        while (currentDfaIndex < dfaList.size()) {
            Dfa currentDfa = dfaList.get(currentDfaIndex);

            //debug start
            boolean debug = false;
            if (currentDfa.stateNum == 5 || currentDfa.stateNum == 7) {
                debug = true;
            }
            //debug end

            for (char asc2char = 0; asc2char <= ASCII_COUNT; asc2char++) {
                //find transferable closure of currentDfa for asc2char
                Set<Nfa> move = nfaInterpreter.move(currentDfa.nfaStates, asc2char);

                if (move.isEmpty()) {
                    System.out.println("DFA from state: " + currentDfa.stateNum + " to state:" + STATE_FAILURE + " on char: " + asc2char);
                    dfaStateTransformTable[currentDfa.stateNum][asc2char] = STATE_FAILURE;
                    continue;
                }

                Set<Nfa> closure = nfaInterpreter.e_closure(move);
                Dfa dfa = alreadyHas(closure);

                if (dfa == null) {
                    System.out.println("Create DFA node:");

                    Dfa newDfa = Dfa.newDfa(closure);

                    printDfa(newDfa);

                    dfaList.add(newDfa);
                    dfaStateTransformTable[currentDfa.stateNum][asc2char] = newDfa.stateNum;

                    continue;
                }

                System.out.println("Get a existed _dfa node:");
                printDfa(dfa);

                dfaStateTransformTable[currentDfa.stateNum][asc2char] = dfa.stateNum;

            }

            System.out.print("\n");
            currentDfaIndex++;
        }

        return dfaStateTransformTable;
    }

    /**
     * @param closure
     * @return the dfa whose nfaStates equals closure from dfaList
     */
    private Dfa alreadyHas(Set<Nfa> closure) {
        for (Dfa dfa : dfaList) {
            if (dfa.hasNfaStates(closure)) {
                return dfa;
            }
        }
        return null;
    }

    private void printDfa(Dfa dfa) {

        System.out.print("Dfa state: " + dfa.stateNum + " its _nfa states are: ");
        Iterator<Nfa> it = dfa.nfaStates.iterator();
        while (it.hasNext()) {
            System.out.print(it.next().getStateNum());
            if (it.hasNext()) {
                System.out.print(",");
            }
        }

        System.out.print("\n");
    }

    public void printDFA() {
        int dfaNum = dfaList.size();
        for (int i = 0; i < dfaNum; i++)
            for (int j = 0; j < dfaNum; j++) {
                if (isOnNumberClass(i, j)) {
                    System.out.println("From state " + i + " to state " + j + " on D");
                }

                if (isOnDot(i, j)) {
                    System.out.println("From state " + i + " to state " + j + " on dot");
                }
            }
    }

    private boolean isOnNumberClass(int from, int to) {
        char c = '0';
        for (c = '0'; c <= '9'; c++) {
            if (dfaStateTransformTable[from][c] != to) {
                return false;
            }
        }

        return true;
    }

    private boolean isOnDot(int from, int to) {
        if (dfaStateTransformTable[from]['.'] != to) {
            return false;
        }

        return true;
    }

    public ArrayList<Dfa> getDfaList() {
        return dfaList;
    }

    public int[][] getDfaTransTable() {
        return dfaStateTransformTable;
    }
}
